Die Nicht-Rekursivität einer Sprache kann man mittels Satz von Rice nachweisen. Wenn es keine Turingmaschine gibt, die ein solches Entscheidungsproblem löst, so gibt es nach der Churchschen These überhaupt keinen Algorithmus für das Problem. Man beschränkt sich bei dieser Definition auf Entscheidungsprobleme, also auf Probleme, deren Antwort ...